package william.binarysearch;

/**
 * @author ZhangShenao
 * @date 2024/3/27
 * @description <a href="https://leetcode.cn/problems/search-insert-position/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 */
public class Leetcode35_搜索插入位置 {
    /**
     * 采用二分搜索法实现
     * 题目的要求是搜索插入位置,等价于寻找第一个>=target元素的位置
     * 维护一个变量firstGE,保存第一个>=target元素的位置
     * 采用二分搜索法,每次找到数组的中点mid,比较mid位置的元素与target元素的大小
     * -如果nums[mid] >= target,则更新firstGE的值,并在左半部分继续查找
     * -否则nums[mid] < target,则在右半部分继续查找
     * 最终返回firstGE
     * <p>
     * 时间复杂度O(logN) 二分搜索的时间复杂度
     * 空间复杂度O(1)
     */
    public int searchInsert(int[] nums, int target) {
        //边界条件校验
        if (nums == null || nums.length < 1) {
            return 0;
        }

        int l = 0;
        int r = nums.length - 1;
        int firstGE = r + 1;    //维护一个变量firstGE,保存第一个>=target元素的位置

        //采用二分搜索法实现
        while (l <= r) {
            //找到数组中点
            int mid = l + ((r - l) >> 1);

            if (nums[mid] >= target) {  //如果nums[mid]>=target,则更新firstGE的值,并在左半部分继续查找
                firstGE = mid;
                r = mid - 1;
            } else {    //否则nums[mid]<target,则在右半部分继续查找
                l = mid + 1;
            }
        }

        //返回firstGE结果
        return firstGE;
    }
}
